package com.lyt.springboot.util.algorithm;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.PriorityQueue;

public class S8 {
    //最小k个数
    public ArrayList<Integer> GetLeastNumbers_Solution(int[] input, int k) {
        ArrayList<Integer> arrayList = new ArrayList<>();
        Arrays.sort(input);
        for (int i = 0; i < k; i++) {
            arrayList.add(input[i]);

        }
        return arrayList;
    }

    //堆排序解决最小的k个数
    public ArrayList<Integer> GetLeastNumbers_Solution1(int[] input, int k) {
        if (input.length<k || k<1) {
            return new ArrayList<>();
        }
        ArrayList<Integer> arr0 = new ArrayList<>();
        if(input.length == k) {
            for (int i = 0; i <input.length ; i++) {
                arr0.add(input[i]);
            }
            return arr0;
        }
        //大顶堆排序
        PriorityQueue<Integer> queue = new PriorityQueue<>((o1, o2) -> o2 - o1);
        for (int i = 0; i < input.length; i++) {
            while(i<k) {
                queue.add(input[i]);
                i++;
            }
            if(queue.peek()>input[i]) {
               queue.poll();
               queue.add(input[i]);
            }
        }
        return new ArrayList<>(queue);
    }


    //第k大的数
    public int findKth(int[] a, int n, int K) {
        // write code here
        //冒泡排序下
        for (int i = 1; i < n; i++) {
            for (int j = 0; j < n - 1; j++) {
                if (a[j] < a[j + 1]) {
                    int temp = a[j];
                    a[j] = a[j + 1];
                    a[j + 1] = temp;
                }
            }

        }
        return a[K-1];
    }

    //使用sort试试  第k大的数
    public int findKth1(int[] a, int n, int K) {
        Arrays.sort(a);
        return a[n-K];
    }

    //堆排序 第k大的数
    public int findKth2(int[] a, int n, int K) {
        PriorityQueue<Integer> queue = new PriorityQueue<>();
        for (int i = 0; i < n; i++) {
            while(i<K) {
                queue.add(a[i]);
                i++;
            }
            if(queue.peek()<a[i]) {
                queue.poll();
                queue.add(a[i]);
            }
        }
        return queue.peek();
    }




    public static void main(String[] args) {
        S8 s8 = new S8();
        int[] arr = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
        int n = 10;
        int k = 4;
        int kth2 = s8.findKth2(arr, n, k);
        int kth = s8.findKth(arr, n, k);
        int kth1 = s8.findKth1(arr, n, k);
        System.out.println(kth);
        System.out.println(kth1);
        System.out.println(kth2);
        ArrayList<Integer> arrayList0 = s8.GetLeastNumbers_Solution(arr, 10);
        ArrayList<Integer> arrayList = s8.GetLeastNumbers_Solution1(arr, 10);
        System.out.println(arrayList0);
        System.out.println(arrayList);
        PriorityQueue<Integer> queue = new PriorityQueue<>(((o1, o2) -> o2 - o1));
        queue.add(5);
        queue.add(4);
        queue.add(7);
        queue.add(9);
        ArrayList<Integer> arr2 = new ArrayList<>(queue);
        System.out.println(arr2);
        System.out.println(queue);
        Integer peek = queue.peek();
        System.out.println(peek);
        queue.poll();
        System.out.println(queue);
        queue.remove();
        System.out.println(queue);
        System.out.println("=================");

    }
}
